package test.algorithm.FastSlowPointer;

/**
 * 希尔排序
 * @author serenity
 *
 */
public class ShellSort {
	
	/**
	 * 希尔排序
	 * @param list
	 */
	public static void shellSort(int[] list){
		int gap = list.length;
		int temp = 0;
		do{
			//增量
			gap = gap/3 + 1;
			for(int i = gap;i<list.length;i++){
				
				if(list[i]<list[i-gap]){
					temp = list[i];
					int j = i-gap;
					
					//比第i个大的元素全部向后移动gap位
					//空出的位置是j+gap
					while(j>=0 && list[j]>temp){
						list[j+gap] = list[j];
						j = j-gap;
					}
					
					//插入第i个元素
					list[j+gap] = temp;
				}
			}
			
		}while(gap>1);
	}
	
	public static void main(String[] args) {
		int[] list = {5,2,6,0,3,9,1,7,4,8};
		shellSort(list);
		
		System.out.print("打印数组：");
		for(int i :list){
			System.out.print(i+" ");
		}

	}

}
